package linklist;

import com.alibaba.fastjson.JSON;
import linklist.SingleNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 描述
 * 给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
 *
 * 数据范围： n<=1000
 * 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。
 *
 * 如当输入链表{1,2,3}时，
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
 *
 * 示例1
 * 输入：{1,2,3}
 * 返回值：{3,2,1}
 *
 * 示例2
 * 输入：{}
 * 返回值：{}
 * 说明：空链表则输出空
 */
public class LinkListDemo {

    //递归反转
    public static SingleNode ReverseListRecursion(SingleNode head) {
        //空或者一个元素
        if (head == null || head.getNext() == null) {
            return head;
        }
        SingleNode res = ReverseListRecursion(head.getNext());
        head.getNext().setNext(head) ;
        head.setNext(null);
        return res;
    }

    //用栈实现
    public static SingleNode ReverseListStack(SingleNode head) {
        //空或者一个元素
        if (head == null || head.getNext() == null) {
            return head;
        }
        Stack<SingleNode> stack = new Stack();
        while(head != null){
            stack.push(head);
            head = head.getNext();
        }
        SingleNode retHeadNode = stack.pop();
        //游标,cur是游标，永远是上一个值
        SingleNode cur = retHeadNode;
        while(!stack.isEmpty()){
            SingleNode node = stack.pop();
            node.setNext(null);
            cur.setNext(node);
            cur = node;
        }
        return retHeadNode;
    }



    public static void main(String[] args) {
        //输出一个链表
        SingleNode singleNode1 = new SingleNode(1);
        SingleNode singleNode2 =new SingleNode(2);
        SingleNode singleNode3 =new SingleNode(3);
        singleNode1.setNext(singleNode2);
        singleNode2.setNext(singleNode3);
        System.out.println(JSON.toJSONString(singleNode1));
        SingleNode reverseNode = ReverseListRecursion(singleNode1);
        System.out.println(JSON.toJSONString(reverseNode));

    }
}
